1. Field of the Invention
The present invention pertains to a numeric value search apparatus and numeric value search method for searching for numeric values of a prescribed rank among multiple digitized numeric value data; and pertains in particular to a numeric value search apparatus and numeric value search method that enable searching for numeric values of a prescribed rank at high speed.
2. Description of the Prior Art
Numeric value data of a prescribed rank from the smallest value, together with mean values, maximum values, and minimum values, are often used in analysis and statistics on numeric value data groups comprised of finite parameters. In particular, the piece of numeric value data with the very middle rank in a numeric value data group is called a median, and may be more useful than a mean value. For example, if a parameter's numeric value data group contains extremely abnormal values, the mean value will be affected by the abnormal values, but the median will not be easily affected.
If the number of parameters is odd, the piece of numeric value data at the ((parameters+1)/2)th place is the median; if the number of parameters is even, then the mean value of the numeric value data at the (parameters/2)th position and the numeric value data at the (parameters/2+1)th position is the median.
In addition, there are numerous methods for searching for medians. The simplest methods include searching for the median by sequentially comparing all numeric value data and rearranging them in ascending order (see, for example, Japanese Laid-open Patent Application 7[1995]-160726 (pages 2–3)), and searching for the median directly.
FIG. 1 illustrates an example configuration for a conventional numeric value search apparatus, which searches for the median directly. In FIG. 1, the memory 10 is a storage unit in which nine pieces of numeric value data d1 through d9 are stored in sequence starting at the first position. Of course, the memory 10 could store a desired number of pieces of numeric value data greater than d1 through d9, but the number is set as nine in order to simplify the explanation. A comparison means 11 reads the numeric value data d1 through d9 from the memory 10 and outputs the median.
The operations of this type of apparatus will now be described below. The comparison means 11 reads the numeric value data d1 which is stored at the first position in the memory 10. It then sequentially reads the numeric value data, d2 through d9, other than the numeric value data d1 (which it has read), comparing them against the numeric value data d1. If there are four pieces of numeric value data, among d2 through d9, which are greater than (or less than) the numeric value data d1, that numeric value data d1 is output as the median.
In this case, if the numeric value data d1 is not the median, then the comparison means 11 reads the numeric value data d2 which is second from the first position of the memory 10. It then sequentially reads the numeric value data, d1 and d3 through d9, other than the numeric value data d2 (which it has read), comparing them against the numeric value data d2. If there are four pieces of numeric value data, among d1 and d3 through d9, which are greater than (or less than) the numeric value data d2, that numeric value data d2 is output as the median.
Next, if the numeric value data d2 is not the median, comparisons are performed in the same manner thereafter on the remaining numeric value data d3 through d9, to determine whether they are the median. Next, the found medians are displayed on a screen (not shown) or output to an external apparatus (not shown).
With this type of apparatus, in order to search for the numeric value data at the (N+1)th position, which is the median, among a number (2N+1) (where N is a positive integer) of parameters, numeric value data readings and comparisons are performed (N×N) times in the worst case, and ((N×N)/2) times on average. If, for example, there are nine parameters, then 16 readings and comparisons are required in the worst case; however, 250,000 are required in the worst case if there are 1001 parameters. Thus, as the number of parameters increases, the time required for searching increases markedly, which has been a problem.
In addition, if analog amounts are digitized for use as numeric value data, the number of pieces of these numeric value data typically increases tremendously in many cases at present, as, for example, in waveform measurement apparatuses such as digital oscilloscopes.
In addition, because searching for a median with the apparatus shown in FIG. 1 is too time consuming, search methods employing frequency distributions (count distributions) are often used. This method focuses on the fact that analog amounts are digitized by, for example, an analog-digital converter and are stored in memory as numeric value data. Specifically, it searches for a median in a frequency distribution, focusing on the fact that the range and resolution of values that can be taken by numeric value data stored in memory are finite.
FIG. 2 is a figure which illustrates an example configuration of a conventional numeric value search apparatus in which such frequency distributions are used. In FIG. 2, the memory 20 is a storage apparatus in which are stored 1001 pieces of digitized numeric value data. Of course, the memory 20 could store a desired number of pieces of numeric value data, but the number is set as 1001 in order to simplify the explanation. The numeric value data are digitized with a resolution of 8 bits (28=256), and the number of different numeric value data values which may be taken is 256. An example of a numeric value data range is the integers from 0 to 255.
A frequency distribution creation unit 30, comprising a counting means 31 and data count region 32, reads the numeric value data of the memory 20 and creates a frequency distribution with the same resolution as that in which the numeric value data were digitized. The counting means 31 increments or clears the corresponding data count region 32 count value based on the numeric value data read from the memory 20. The data count region 32 comprises 256 count value holding means, C0 through C255, which have the same resolution as that in which the numeric value data were digitized; they are counted or cleared by the counting means 31, and hold count values.
A computation unit 40 computes the median from the count values of the count value holding means C0 through C255 in the data count region 32 of the frequency distribution creation unit 30.
The operations of such an apparatus will now be described.
The counting means 31 clears to “0” all of the count values of the count value holding means C0 through C255 of the data count region 32. Next, the counting means 31 sequentially reads the numeric value data from the memory 20, and increments the count value in the count value holding means C0 through C255 which corresponds to the read numeric value data. For example, if the numeric value data is “8”, then the value of the count value holding means C8 is incremented; if the numeric value data is “255”, then the value of the count value holding means C255 is incremented.
In this case, if the count values of the count value holding means C0 through C255 when the counting means 31 finishes counting all of the numeric value data in the memory 20, i.e., their frequencies, are respectively Cd0 through Cd255, then the frequency distribution is represented by the histogram shown in FIG. 3. FIG. 3 is a histogram representing the frequency distribution created by the frequency distribution creation unit 30. In FIG. 3, the count value holding means C0 through C255 are on the horizontal axis, and the frequencies (count values) are on vertical axis.
Next, the computation unit 40 sequentially reads the count values Cd0 through Cd255 of the count value holding means C0 through C255, accumulates them, and computes the median. Specifically, as is apparent from the histogram shown in FIG. 3, the numeric value data, corresponding to the count value holding means Cm (where m is a natural number such that 1≦m≦255) satisfying equation (1) below, is the median, which is at the (N+1)th place in the (2N+1) pieces of numeric value data.(N+1)≦Cd0orCd0+Cd1+ . . . +Cd(m−1)<(N+1)≦Cd0+Cd1+ . . . +Cd(m−1)+Cdm  (1)
Accordingly, even if the number of pieces of parameter numeric value data is numerous at 1001 pieces, in the search by the numeric value search apparatus shown in FIG. 2, there are 1001 readings, 1001 incrementings by the data count region 32, and the computation unit 40 performs reading and accumulation 255 times at worst. Thus if the frequency distribution creation resolution is p (where p is a natural number), then the number of executions of reading, writing, accumulation and the like is expressed as (2×(2N+1)+(2p−1), and even if the number of parameters increases, the time required for searching will never increase exponentially in comparison to the numeric value search apparatus shown in FIG. 1.
This type of median search is also used in waveform measurement apparatuses. A waveform measurement apparatus digitized a measured waveform (analog amount) by means of an analog/digital converter to change it to numeric value data; stores it in the memory 20; and furthermore performs prescribed processes and analysis based on the numeric value data stored in the memory 20 and displays the waveform.
If, for example, multiple waveform measurements are taken using a trigger signal as a reference signal, then in order to reduce the effects of noise, it may be better to use a median than to determine a mean value in the numeric value data occurring at the same time from the trigger signal. Of course, the number of pieces of digitized numeric value data is enormous, but it is necessary to collect as much data as possible on the rapidly changing measured waveforms without downsampling. For this reason, the apparatus shown in FIG. 2 is used to perform the median search as rapidly as possible.
However, in recent years, there has been an increase in the resolution when analog amounts are digitized. In addition, in waveform measurement apparatuses, even if the resolution during digitization is 8 bits, it has become common for the resolution to have more bits for reasons related to numeric value data processing, or as a result of numeric value data processing. For example, in some cases the resolution is 16 bits (216=65,536).
With such resolutions, the computation of the cumulative value by the computation unit 40 after creation has become more influential than the frequency distribution created by the frequency distribution creation unit 30, with respect to the median search. Specifically, the computation unit 40 reads and accumulates the count value from the data count region 32, which comprises 65,536 count value holding means having a resolution which is the same as that at which the numeric value data were digitized. Because of this, the required computation time is 65,535 times in the worst case, and 32,768 times even on average. Thus even if the parameters creating the frequency distribution are constant, if the resolution increases, the cumulative computation of the computation unit 40 increases, making the median search extremely time-consuming, which has been a problem.